With the advent of large-scale integrated (LSI) and very large-scale integrated (VLSI) circuitry, there has been the need to route the connections between the terminals of the microelectronic circuitry contained within the integrated circuit and the bonding pads on the periphery of the circuit chip. In the manufacture of an integrated circuit, small wires are connected between the bonding pads and the leads on the chip carrier, thereby allowing power and ground to be applied to the integrated circuit and signals to be fed to and received from the integrated circuit. The chip area consumed by the connections between the terminals on the core module containing the microelectronic circuitry and the pads on the array of pads surrounding the core module can strongly influence the overall size of the chip. The chip size, in turn, affects the number of integrated circuits that can be designed within a given amount of substrate area, and it is therefore desirable to make the chip as small as possible.
Routing was originally done by experienced workers. More recently, however, as the number of terminals and pads increases along with the complexity of the microelectronic circuitry, the routing task has been given over to computer-aided design systems. This is particularly the case for an integrated circuit compiler system where the results of the compilation are highly dependent upon the specifics of the circuit being designed.
Several approaches to automated routing have been taken. In one of the most popular, routing has been done using channel routers. The area between the core module terminals and the array of pads can be subdivided into four channels, each channel having two sides. One side of each channel contains the terminals found along one side of the core module of the integrated circuit, while the other side of the channel contains the pads in the array of pads facing that particular side of the core module. Channel routing does not perform acceptably in routing VLSI circuits. This is because a channel router is incapable of efficiently accounting for terminals and pads that lie along the sides of the other channels that define the area between the core module and the array of pads but are connected by signal or power nets to terminals or pads along the sides of the channel being routed.
Other approaches to the routing problem were taken by Lee and Hightower. In the method developed by Lee, for example, beginning and ending points of a path are specified in a rectangular grid, as well as the occupied portions of the area between the beginning and ending points. The shortest path between the beginning and ending points is then determined by an ever-expanding "wavefront" that emanates from the beginning point and continues to propagate until it reaches the specified ending point. Unfortunately, both the Lee and Hightower methods are computationally Lee, for example, beginning and ending points are specified in a rectangular grid, and occupied portions of the area between the beginning and ending points are specified, the shortest path between the beginning and ending point is determined by an ever-expanding "wavefront" that emanates from the beginning point and continues to propagate until it reaches the specified ending point. Unfortunately, both the Lee and Hightower methods are computationally inefficient and consume a great deal of memory.
More recently, channel routers have been used to solve a form of the channel routing problem wherein pads along a top wall of the channel are connected with terminals along the bottom wall by means of signal nets belonging to a predetermined net list. The net list contains a specification of the nets and their connections to pads and terminals on the channel walls. In this approach, two layers are available for routing. It is assumed that the horizontal tracks are formed on one layer, while the vertical columns are formed on the other. The horizontal tracks are isolated from the vertical columns although they can be connected through via holes. Two nets in the net list are said to be constrained if they have corresponding end points on the same vertical column.
A vertical constraint graph can be developed from the net list representation for a particular routing problem. The vertical constraint graph has a node for each net in the net list and a directed edge from a first node to a second node if the corresponding first net must be placed above the corresponding second net in the channel. The vertical constraint graph immediately identifies cyclic constraints, such as nets which are each respectively constrained to be above the other. The vertical constraint graph also identifies cyclic constraints involving three and more nets.
In the "left edge algorithm" method, developed by Hashimoto and Stevens in "Wire Routing by Optimizing Channel Assignment," proceedings of the 8th Design Automation Conference, 1971, pages 214-224, and later improved by Yoshimura in "An Efficient Channel Router," Proceedings of 21st Design Automation Conference, 1984, pages 38-44, a simple and efficient channel router is presented. This channel router guarantees that all nets will be completed if there are no cyclic constraints and the channel height is adjustable. The channel router can be used in the layout design of custom chips as well as uniform structures such as gate arrays. Unfortunately, however, the channel router is unable to properly account for the constraints imposed on nets which must connect terminals or pads in one channel with terminals or pads in another channel.
In another approach, discussed by Rosenberg in "Chip Assembly Techniques for Custom IC Design and a Symbolic Virtual-Grid Environment," 1984 Conference on Advanced Research in VLSI, MIT, the "square doughnut" domain (or moat) formed between the pads and the chip is mapped onto a simple rectangle. This mapping function has to treat the rectangular channel as the sides of a cylinder, with the edges at the ends of the rectangle being connected to each other. The mapping functions must also deal with the corners of the "square doughnut" very carefully. They must map to a single line in the "rectangular channel" domain. Unfortunately, this approach does not guarantee that the nets will be 100 percent routed.
In "A New Area Router, the LRS Algorithm," IEEE International Conference on Circuits and Computers, September-October, 1982, Smith et al. discuss an algorithm that takes advantage of the "radial symmetry" of area routing problems. The first step in this approach is to assign each net to its own "circular" track. Each track is actually square in shape and centered around the middle of the routing region. Succeeding tracks are added outwardly from the center of the routing region. A net can be assigned to a particular track only if each of the pins in that net can be connected to the track by using a single radial segment. Thus, for any given track, there may be several nets that could be assigned to it. While this paper discloses the use of concentric tracks, it does not disclose a routing technique that guarantees 100-percent routing.
Accordingly, it is desirable to have a moat channel router that is based on an efficient channel routing algorithm with additional features addressing the characteristics of the moat area configuration, while minimizing chip area and guaranteeing 100-percent routing completion.